#include<bits/stdc++.h>
using namespace std;

typedef struct {//哈夫曼树的节点
    string data;
    int parent;
    int left;
    int right;
    int value;
}treenode;

typedef struct {//哈夫曼编码的值
    string s;
}treecode;

void createTree(treenode arr[], int n) {//构造哈夫曼树
    for (int i = 0; i < 2 * n - 1; i++) {//初始化这些节点的parent和child
        arr[i].parent = arr[i].left = arr[i].right = -1;  
    }
    for (int i = n; i < 2 * n - 1; i++) {
        int min1 = INT_MAX, min2 = INT_MAX;//左节点<右节点
        int l = -1, r = -1;
        for (int j = 0; j <= i - 1; j++) {//选择两个最小的节点
            if (arr[j].parent == -1) {//如果这个结点没有用过
                if (arr[j].value < min1) {//如果比左节点小
                    min2 = min1;
                    r = l;
                    min1 = arr[j].value;
                    l = j;
                }
                else if (arr[j].value < min2) {//如果比右节点小
                    min2 = arr[j].value;
                    r = j;
                }
            }
        }
        arr[i].value = arr[l].value + arr[r].value;
        arr[i].left = l, arr[i].right = r;
        arr[l].parent = i, arr[r].parent = i;
    }
}

void createCode(treenode arr[],treecode code[], int n) {
    for (int i = 0; i < n; i++) {//从叶子节点开始
        int childIndex = i;
        int parentIndex = arr[i].parent;//当前节点的父节点位置
        while (parentIndex != -1) {//未到根节点
            if (arr[parentIndex].left == childIndex) {//如果当前节点的值是左节点
                code[i].s += "0";
            }
            else {//如果当前节点的值是右节点
                code[i].s += "1";
            }
            childIndex = parentIndex;
            parentIndex = arr[parentIndex].parent;
        }
    }
}

int main() {
    vector<string>str = {"The","of","a","to","and","in","that","he","is","at","on","for","His","are","be"};
    int valuearr[] = { 1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123 };
    int len = 15;
    treenode arr[100];
    treecode code[100];
    for (int i = 0; i < len; i++) {
        arr[i].data = str[i];
        arr[i].value = valuearr[i];
    }
    createTree(arr, len);
    createCode(arr, code, len);

    int sumpath = 0;
    int sumvalue = 0;
    cout << "哈夫曼编码为：" << endl;
    for (int i = 0; i < len; i++) {
        cout << arr[i].data << '\t' << code[i].s << endl;
        sumvalue += arr[i].value;
        sumpath += arr[i].value * code[i].s.length();
    }
    cout << "平均长度为：" << 1.0 * sumpath / sumvalue;
    return 0;
}
